import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 喧闹和富有 {
    //https://leetcode.cn/problems/loud-and-rich/description/
    //拓扑排序
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        //动态表 + 入度图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] indegress = new int[n];
        //填入度图和构建图
        for(int[] num: richer){
            graph.get(num[0]).add(num[1]);
            indegress[num[1]]++;
        }
        //加入入度为0的
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if(indegress[i] == 0){
                queue.add(i);
            }
        }
        //初始化ans的值, 每个值开始都是自己
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = i;
        }
        //不断遍历
        while(!queue.isEmpty()){
            int t = queue.poll();
            for(int num : graph.get(t)){
                //如果有钱的比自己还要安静
                //就将quiet值修改成安静的, ans的值也修改成安静的
                if(quiet[t] < quiet[num]){
                    ans[num] = ans[t];
                    quiet[num] = quiet[t];
                }
                //入度为0加入队列中
                if(--indegress[num] == 0){
                    queue.add(num);
                }
            }
        }
        return ans;
    }
}
